package com.itheima;


import org.junit.Test;
import sun.misc.SoftCache;

import javax.swing.tree.TreeNode;
import java.io.*;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.util.*;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.stream.Stream;

public class testLecode {

    @Test
    public void testtest() throws ExecutionException, InterruptedException {
        trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
    }

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int i = 0;
        int j = 0;
        while (i < s.length) {
            if (j == g.length - 1) {
                break;
            }
            if (g[j] <= s[i]) {
                j++;
                i++;
                count++;
            } else {
                i++;
            }

        }
        return count;
    }

    public int wiggleMaxLength(int[] nums) {
        int dis[] = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            dis[i] = nums[i] - nums[i - 1];
        }
        int count = 0;
        int temp = 0;
        for (int i = 1; i < dis.length; i++) {
            if (dis[i] == 0) {
                continue;
            }
            if (i == 1) {
                count++;
                temp = dis[i] > 0 ? 1 : -1;
            }

            if (temp == 1 && dis[i] < 0) {
                count++;
                temp = -1;
            }
            if (temp == -1 && dis[i] > 0) {
                count++;
                temp = 1;
            }
        }
        return count + 1;
    }

    public int maxSubArray(int[] nums) {
        int nowSum = nums[0];
        int maxSum = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            if (nowSum < 0 && nums[i] > nowSum) {
                nowSum = nums[i];
            } else {
                nowSum += nums[i];
            }
            maxSum = Math.max(maxSum, nowSum);
        }
        return maxSum;
    }


    public boolean canJump(int[] nums) {
        int[] temp = new int[nums.length];
        temp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (temp[i - 1] == i && nums[i] == 0) {
                return false;
            }
            if (nums[i] + i > temp[i - 1]) {
                for (int j = i; j >= 0; j--) {
                    temp[j] = nums[i] + i;
                }
            } else {
                temp[i] = temp[i - 1];
            }
        }
        return true;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasSum = Arrays.stream(gas).sum();
        int costSum = Arrays.stream(cost).sum();
        if (gasSum < costSum) {
            return -1;
        }
        int[] temp = new int[gas.length];
        for (int i = 0; i < gas.length; i++) {
            temp[i] = gas[i] - cost[i];
        }
        for (int i = 0; i < gas.length; i++) {
            if (temp[i] < 0 || temp[i] + temp[(i + 1) % gas.length] < 0) {
                continue;
            } else {
                if (isOk(temp, i)) {
                    return i;
                }
            }
        }
        return -1;
    }

    private boolean isOk(int[] temp, int startIndex) {
        int nowGap = temp[startIndex];
        for (int i = 0; i < temp.length - 2; i++) {
            nowGap += temp[(startIndex + 1) % temp.length];
            if (nowGap < 0) {
                return false;
            }
            if (nowGap == 0 && i != temp.length - 2) {
                return false;
            }
            startIndex++;
        }
        return true;
    }

    public int candy(int[] ratings) {
        int[] temp = new int[ratings.length];
        Arrays.fill(temp, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                temp[i] = temp[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i > -1; i--) {
            if (ratings[i] > ratings[i + 1]) {
                temp[i] = Math.max(temp[i], temp[i + 1] + 1);
            }
        }
        return Arrays.stream(temp).sum();

    }

    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                five++;
            }
            if (bills[i] == 10) {
                ten++;
                five--;
            }
            if (bills[i] == 20) {
                if (ten > 0) {
                    ten--;
                    five--;
                } else {
                    five -= 3;
                }
            }
            if (five < 0 || ten < 0) {
                return false;
            }
        }
        return true;
    }

    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(value -> value[0]));
        int end = points[0][1];
        int count = 1;
        for (int i = 1; i < points.length; i++) {
            if (end >= points[i][1]) {
                end = points[i][1];
            } else if (end >= points[i][0] && end <= points[i][1]) {
                continue;
            } else {
                end = points[i][1];
                count++;
            }
        }
        return count;
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(value -> value[0]));
        int end = intervals[0][1];
        int count = 1;
        for (int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][1]) {
                end = intervals[i][1];
            } else if (end >= intervals[i][0] && end <= intervals[i][1]) {
                continue;
            } else {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.length - count;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int hash[] = new int[27];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a'] = i;
        }
        int end = hash[s.charAt(0) - 'a'];
        int lastEnd = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i == end) {
                result.add(end + 1 - lastEnd);
                lastEnd = end + 1;
                if (i < s.length() - 1) {
                    end = hash[s.charAt(i + 1) - 'a'];
                }
            } else {
                if (hash[s.charAt(i) - 'a'] > end) {
                    end = hash[s.charAt(i) - 'a'];
                }
            }
        }
        return result;
    }

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));
        int count = 0;
        List<int[]> temResult = new ArrayList<int[]>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > end) {
                temResult.add(new int[]{start, end});
                count++;
                start = intervals[i][0];
                end = intervals[i][1];
            }
            if (intervals[i][1] > end) {
                end = intervals[i][1];
            }
        }
        if (count == 0) {
            temResult.add(new int[]{start, end});
        } else if (((int[]) temResult.get(count - 1))[1] != end) {
            temResult.add(new int[]{start, end});
        }
        int[][] result = new int[temResult.size()][2];
        int index = 0;
        for (int[] o : temResult) {
            result[index++] = o;
        }
        return result;
    }

    public int monotoneIncreasingDigits(int n) {
        int index = 0;
        int lastIndex = 0;
        int[] temp = new int[10];
        int lastCount = Integer.MAX_VALUE;
        while (n != 0) {
            int nowCount = n % 10;
            if (nowCount <= lastCount) {
                temp[index++] = nowCount;
                lastCount = nowCount;
            } else {
                nowCount -= 1;
                for (int i = lastIndex; i < index; i++) {
                    temp[i] = 9;
                }
                lastCount = nowCount;
                lastIndex = index;
                temp[index++] = nowCount;
            }
            n /= 10;
        }
        int count = 0;
        for (int i = 0; i < index; i++) {
            count += temp[i] * Math.pow(10, i);
        }
        return count;
    }

    public int fib(int n) {
        int[] temp = new int[n + 1];
        temp[0] = 0;
        temp[1] = 1;
        for (int i = 2; i <= n; i++) {
            temp[i] = temp[i - 1] + temp[i - 2];
        }
        return temp[n];
    }

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] dp = new int[n + 1];
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 0;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = 1;
            } else {
                break;
            }
        }
        for (int i = 0; i < col; i++) {
            if (obstacleGrid[0][i] == 0) {
                dp[0][i] = 1;
            } else {
                break;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[row - 1][col - 1];
    }

    public int integerBreak(int n) {
        int dp[] = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            int temMax = 0;
            for (int j = 1; j <= i / 2; j++) {
                int nowMax = Math.max(j * (i - j), j * dp[i - j]);
                temMax = Math.max(temMax, nowMax);
            }
            dp[i] = temMax;
        }
        for (int i : dp) {
            System.out.println(i);
        }
        return dp[n];
    }

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = dp[i] + dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        Arrays.sort(nums);
        int dp[][] = new int[nums.length][target + 1];
        for (int i = 1; i < target + 1; i++) {
            if (i >= nums[0]) {
                dp[0][i] = nums[0];
            }
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j < target + 1; j++) {
                if (j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }
            }
        }
        return dp[nums.length - 1][target] == target;
    }

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(sum) < Math.abs(target)) {
            return 0;
        }
        if ((sum - target) % 2 != 0) {
            return 0;
        }

        int backpack = (sum - target) / 2 + target;
        int dp[] = new int[backpack + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = backpack; j >= nums[i]; j--) {
                if (nums[i] == 0 && j == 0) {
                    dp[j] = 2 * dp[j];
                    continue;
                }
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[backpack];
    }

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

    public int combinationSum4(int[] nums, int target) {
        int dp[] = new int[target + 1];
        dp[0] = 1;
        for (int j = 1; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j >= nums[i]) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int dp[] = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (j == coins[i]) {
                    dp[j] = 1;
                    continue;
                }
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];

    }

    public int numSquares(int n) {
        int max = (int) Math.sqrt(n);
        int dp[] = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i <= max; i++) {
            int count = i * i;
            for (int j = count; j <= n; j++) {
                if (j == count) {
                    dp[j] = 1;
                }
                if (dp[j - count] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - count] + 1);
                }
            }
        }
        return dp[n];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean db[] = new boolean[s.length() + 1];
        db[0] = true;
        for (int j = 1; j <= s.length(); j++) {
            for (int i = 0; i < wordDict.size(); i++) {
                int length = wordDict.get(i).length();
                if (j < length) {
                    continue;
                }
                if (s.substring(0, j).equals(wordDict.get(i))) {
                    db[j] = true;
                    continue;
                }
                if (s.substring(j - length, j).equals(wordDict.get(i)) && db[j - length]) {
                    db[j] = true;
                }
            }
        }
        return db[s.length()];
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int rob(TreeNode root) {
        int[] dp = backTracking(root);
        return Math.max(dp[0], dp[1]);
    }

    //0不偷  1偷
    private int[] backTracking(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = backTracking(root.left);
        int[] right = backTracking(root.right);
        final int[] dp = new int[2];
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = root.val + left[0] + right[0];
        return dp;
    }


    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], prices[i] + dp[i - 1][2]);
        }
        return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][3]);
    }

    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length][2 * k];
        for (int i = 0; i < k; i++) {
            dp[0][2 * i] = -prices[0];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < k; j++) {
                if (j == 0) {
                    dp[i][j * 2] = Math.max(dp[i - 1][j * 2], -prices[i]);
                } else {
                    dp[i][j * 2] = Math.max(dp[i - 1][j * 2], dp[i - 1][j * 2 - 1] - prices[i]);
                }
                dp[i][j * 2 + 1] = Math.max(dp[i - 1][j * 2 + 1], prices[i] + dp[i - 1][j * 2]);
            }
        }
        int result = 0;
        for (int i = 1; i < 2 * k; i += 2) {
            if (dp[prices.length - 1][i] > result) {
                result = dp[prices.length - 1][i];
            }
        }
        return result;
    }

    //    public int maxProfit(int[] prices) {
//        if (prices == null || prices.length < 2) {
//            return 0;
//        }
//        int[][]dp=new int[prices.length][2];
//        dp[0][0]=-prices[0];
//        dp[0][1]=0;
//        dp[1][0]=Math.max(dp[0][0],-prices[1]);
//        dp[1][1]=Math.max(dp[0][1],dp[0][0]+prices[1]);
//        for (int i=2;i<prices.length;i++){
//            dp[i][0]=Math.max(dp[i-1][0],dp[i-2][1]-prices[i]);
//            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
//        }
//        return dp[prices.length-1][1];
//    }
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0] - fee;
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
        }
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);

    }

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int result = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }

    public int findLengthOfLCIS(int[] nums) {
        int dp[] = new int[nums.length];
        dp[0] = 1;
        int result = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }

    public int findLength(int[] nums1, int[] nums2) {
        int result = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result;
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i < text1.length() + 1; i++) {
            for (int j = 1; j < text2.length() + 1; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return dp[text1.length()][text2.length()];
    }

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int dp[][] = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }

//    public int maxSubArray(int[] nums) {
//        int dp[]=new int[nums.length+1];
//        int max=nums[0];
//        int temp=0;
//        for (int i=1;i<=nums.length;i++){
//            if(temp<=0){
//                dp[i]=nums[i-1];
//                temp=nums[i-1];
//            }else {
//                dp[i]=nums[i-1]+temp;
//                temp=nums[i-1]+temp;
//            }
//            max=Math.max(max,temp);
//        }
//        return max;
//    }
//

    public boolean isSubsequence(String s, String t) {
        int dp[][] = new int[s.length() + 1][t.length() + 1];
        int max = 0;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max == s.length();
    }

    public int numDistinct(String s, String t) {
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        for (int i = 1; i <= t.length(); i++) {
            for (int j = 1; j <= s.length(); j++) {
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    if (i == 1) {
                        dp[i][j] = dp[i][j - 1] + 1;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[t.length()][s.length()];
    }


    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        for (int i = 0; i <= word1.length(); i++) {
            for (int j = 0; j <= word2.length(); j++) {
                System.out.print(dp[i][j] + "  ");
            }
            System.out.println();
        }
        return dp[word1.length()][word2.length()];
    }


    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { //情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }

    public int longestPalindromeSubseq(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        int[][] dp = new int[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i >= 1) {
                        dp[i][j] = j - i + 2;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int result[] = new int[temperatures.length];
        Arrays.fill(result,-1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                while (!stack.isEmpty()) {
                    if (temperatures[i] >= temperatures[stack.peek()]) {
                        int index = stack.pop();
                        result[index] = i;
                    } else {
                        stack.push(i);
                        break;
                    }
                }
                if (stack.isEmpty()) {
                    stack.push(i);
                }
            }
        }
        return result;
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Arrays.fill(result, -1);
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }
        for (int i = 0; i < nums2.length; i++) {
                while (!queue.isEmpty()) {
                    if (nums2[i] > queue.peek()) {
                        int count = queue.pop();
                        if (map.containsKey(count)) {
                            int index = map.get(count);
                            result[index] = nums2[i];
                        }
                    } else {
                            queue.add(nums2[i]);
                    }
                }
                if(queue.isEmpty()){
                    queue.add(nums2[i]);
                }
        }
        return result;
    }

    public int[] nextGreaterElements(int[] nums) {
        int result[]=new int[nums.length];
        Arrays.fill(result,-1);
        Deque<Integer> stack=new ArrayDeque<>();
        for (int i=0;i<nums.length;i++){
            fillResult(result,stack,nums,i);
        }
        for (int i=0;i<nums.length;i++){
            fillResult(result,stack,nums,i);
        }
        return result;
    }
    public void fillResult(int []result,Deque<Integer>stack,int []nums,int i){
        if(stack.isEmpty()){
            stack.push(i);
        }else{
            while (!stack.isEmpty()){
                if(nums[i]>nums[stack.peek()]){
                    int index=stack.pop();
                    result[index]=nums[i];
                }else {
                    stack.push(i);
                    break;
                }
            }
            if(stack.isEmpty()){
                stack.push(i);
            }
        }
    }
    public int trap(int[] height) {
         int[] result = dailyTemperatures(height);
         int countResult=0;
         for (int i=0;i<result.length;i++){
             if(result[i]==-1||height[i]==0){
                 continue;
             }else {
                 int index=result[i];
                 int length=index-i-1;
                 int tempCount=length*height[i]-getCount(height,i,index);
                 countResult+=tempCount;
                 i=index-1;
             }
         }
         return countResult;
    }
    public int getCount(int[]height,int from,int end){
        int count=0;
        for (int i=from+1;i<end;i++){
            count+=height[i];
        }
        return count;
    }



}






